package com.example.demo.arithmetic;

/**
 * Description: <br/>
 *
 * @author liulonglong<br   />;
 * @taskId <br/>
 * @Date 2019/5/14 11:19
 * @Version 1.0
 */
public class ArrayTest2 {
    /**
     * 方式一
     * 实现原理是：两个变量记录左右节点，两边分别开始遍历。左边的节点遇到负值继续前进，遇到正值停止。右边的节点正好相反。
     * 然后将左右节点的只进行交换，然后再开始遍历直至左右节点相遇。
     * 这种方式的时间复杂度是O(n).空间复杂度为O(1)
     *
     * @param a     要排列数组
     * @param left  左开始索引
     * @param right 右开始索引
     */
    public static void setParted1(int[] a, int left, int right) {
        if (left >= right || left == a.length || right == 0) {
            for (int i = 0; i < a.length; i++) {
                System.out.println(a[i]);
            }
            return;
        }
        while (a[left] < 0) {
            left++;
        }
        while (a[right] >= 0) {
            right--;
        }
        if (left >= right || left == a.length || right == 0) {
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i] + "\t");
            }
            System.out.println();
            return;
        }
        swap(a, left, right);
        left++;
        right--;
        setParted1(a, left, right);
    }

    private static void swap(int a[], int left, int right) {
        int temp = 0;
        temp = a[left];
        a[left] = a[right];
        a[right] = temp;
    }

    /**
     * 方式二
     */
    public static void setParted(int[] a) {
        int temp = 0;
        int border = -1;

        for (int i = 0; i < a.length; i++) {
            if (a[i] < 0) {
                temp = a[i];
                a[i] = a[border + 1];
                a[border + 1] = temp;
                border++;
            }
        }
        for (int j = 0; j < a.length; j++) {
            System.out.print(a[j] + "\t");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int a[] = { 1, 2, -1, -5, -6, 7, -7, -10 };
        int b[] = { 8, 7, -1, -2, -3, -9, -8, -7, 2, 3, 9, 8 };
        setParted(a);
        setParted1(b, 0, b.length - 1);
    }

}
